{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "===============================================================================\n",
      "                                     CVXPY                                     \n",
      "                                     v1.2.0                                    \n",
      "===============================================================================\n",
      "(CVXPY) May 22 12:36:31 PM: Your problem has 5 variables, 3 constraints, and 0 parameters.\n",
      "(CVXPY) May 22 12:36:31 PM: It is compliant with the following grammars: DCP, DQCP\n",
      "(CVXPY) May 22 12:36:31 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)\n",
      "(CVXPY) May 22 12:36:31 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.\n",
      "-------------------------------------------------------------------------------\n",
      "                                  Compilation                                  \n",
      "-------------------------------------------------------------------------------\n",
      "(CVXPY) May 22 12:36:31 PM: Compiling problem (target solver=GLPK_MI).\n",
      "(CVXPY) May 22 12:36:31 PM: Reduction chain: Dcp2Cone -> CvxAttr2Constr -> ConeMatrixStuffing -> GLPK_MI\n",
      "(CVXPY) May 22 12:36:31 PM: Applying reduction Dcp2Cone\n",
      "(CVXPY) May 22 12:36:31 PM: Applying reduction CvxAttr2Constr\n",
      "(CVXPY) May 22 12:36:31 PM: Applying reduction ConeMatrixStuffing\n",
      "(CVXPY) May 22 12:36:31 PM: Applying reduction GLPK_MI\n",
      "(CVXPY) May 22 12:36:31 PM: Finished problem compilation (took 5.029e-03 seconds).\n",
      "-------------------------------------------------------------------------------\n",
      "                                Numerical solver                               \n",
      "-------------------------------------------------------------------------------\n",
      "(CVXPY) May 22 12:36:31 PM: Invoking solver GLPK_MI  to obtain a solution.\n",
      "-------------------------------------------------------------------------------\n",
      "                                    Summary                                    \n",
      "-------------------------------------------------------------------------------\n",
      "(CVXPY) May 22 12:36:31 PM: Problem status: optimal\n",
      "(CVXPY) May 22 12:36:31 PM: Optimal value: -3.300e+02\n",
      "(CVXPY) May 22 12:36:31 PM: Compilation took 5.029e-03 seconds\n",
      "(CVXPY) May 22 12:36:31 PM: Solver (including time spent in interface) took 0.000e+00 seconds\n",
      "收益最优值为： 330.0\n",
      "投资最优解为 [1. 0. 0. 0. 1.]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\goodboy\\AppData\\Local\\Programs\\Python\\Python39\\lib\\site-packages\\cvxpy\\expressions\\expression.py:593: UserWarning: \n",
      "This use of ``*`` has resulted in matrix multiplication.\n",
      "Using ``*`` for matrix multiplication has been deprecated since CVXPY 1.1.\n",
      "    Use ``*`` for matrix-scalar and vector-scalar multiplication.\n",
      "    Use ``@`` for matrix-matrix and matrix-vector multiplication.\n",
      "    Use ``multiply`` for elementwise multiplication.\n",
      "This code path has been hit 15 times so far.\n",
      "\n",
      "  warnings.warn(msg, UserWarning)\n",
      "C:\\Users\\goodboy\\AppData\\Local\\Programs\\Python\\Python39\\lib\\site-packages\\cvxpy\\expressions\\expression.py:593: UserWarning: \n",
      "This use of ``*`` has resulted in matrix multiplication.\n",
      "Using ``*`` for matrix multiplication has been deprecated since CVXPY 1.1.\n",
      "    Use ``*`` for matrix-scalar and vector-scalar multiplication.\n",
      "    Use ``@`` for matrix-matrix and matrix-vector multiplication.\n",
      "    Use ``multiply`` for elementwise multiplication.\n",
      "This code path has been hit 16 times so far.\n",
      "\n",
      "  warnings.warn(msg, UserWarning)\n"
     ]
    }
   ],
   "source": [
    "#6.1\n",
    "\n",
    "#参考模型：https://www.doc88.com/p-7844984057765.html\n",
    "#x[j]0或1表示是否对该项目进行投资\n",
    "import cvxpy as cp\n",
    "import numpy as np\n",
    "c = np.array([-150,-210,-60,-80,-180]) #定义目标向量\n",
    "a = np.array([[210,300,100,130,260],[1,1,1,0,0],[0,0,0,1,1],[-1,0,0,0,1]])#定义约束矩阵\n",
    "b = np.array([600,1,1,0])#定义右边约束矩阵\n",
    "x = cp.Variable(5,integer=True)#定义五个整型变量\n",
    "obj = cp.Minimize(c*x)#构造目标函数\n",
    "cons =[a*x <= b,x>=0,x<=1]#构造约束条件\n",
    "prob = cp.Problem(obj,cons)#构造问题模型\n",
    "prob.solve(solver = 'GLPK_MI',verbose = True)#求解问题\n",
    "print('收益最优值为：',-prob.value)\n",
    "print('投资最优解为',x.value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "===============================================================================\n",
      "                                     CVXPY                                     \n",
      "                                     v1.2.0                                    \n",
      "===============================================================================\n",
      "(CVXPY) May 22 12:39:59 PM: Your problem has 6 variables, 3 constraints, and 0 parameters.\n",
      "(CVXPY) May 22 12:39:59 PM: It is compliant with the following grammars: DCP, DQCP\n",
      "(CVXPY) May 22 12:39:59 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)\n",
      "(CVXPY) May 22 12:39:59 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.\n",
      "-------------------------------------------------------------------------------\n",
      "                                  Compilation                                  \n",
      "-------------------------------------------------------------------------------\n",
      "(CVXPY) May 22 12:39:59 PM: Compiling problem (target solver=GLPK_MI).\n",
      "(CVXPY) May 22 12:39:59 PM: Reduction chain: Dcp2Cone -> CvxAttr2Constr -> ConeMatrixStuffing -> GLPK_MI\n",
      "(CVXPY) May 22 12:39:59 PM: Applying reduction Dcp2Cone\n",
      "(CVXPY) May 22 12:39:59 PM: Applying reduction CvxAttr2Constr\n",
      "(CVXPY) May 22 12:39:59 PM: Applying reduction ConeMatrixStuffing\n",
      "(CVXPY) May 22 12:39:59 PM: Applying reduction GLPK_MI\n",
      "(CVXPY) May 22 12:39:59 PM: Finished problem compilation (took 6.003e-03 seconds).\n",
      "-------------------------------------------------------------------------------\n",
      "                                Numerical solver                               \n",
      "-------------------------------------------------------------------------------\n",
      "(CVXPY) May 22 12:39:59 PM: Invoking solver GLPK_MI  to obtain a solution.\n",
      "-------------------------------------------------------------------------------\n",
      "                                    Summary                                    \n",
      "-------------------------------------------------------------------------------\n",
      "(CVXPY) May 22 12:39:59 PM: Problem status: optimal\n",
      "(CVXPY) May 22 12:39:59 PM: Optimal value: -1.000e+01\n",
      "(CVXPY) May 22 12:39:59 PM: Compilation took 6.003e-03 seconds\n",
      "(CVXPY) May 22 12:39:59 PM: Solver (including time spent in interface) took 9.964e-04 seconds\n",
      "总收入最优值为： 10.0\n",
      "选运最优解为 [1. 0. 0. 1. 0. 1.]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\goodboy\\AppData\\Local\\Programs\\Python\\Python39\\lib\\site-packages\\cvxpy\\expressions\\expression.py:593: UserWarning: \n",
      "This use of ``*`` has resulted in matrix multiplication.\n",
      "Using ``*`` for matrix multiplication has been deprecated since CVXPY 1.1.\n",
      "    Use ``*`` for matrix-scalar and vector-scalar multiplication.\n",
      "    Use ``@`` for matrix-matrix and matrix-vector multiplication.\n",
      "    Use ``multiply`` for elementwise multiplication.\n",
      "This code path has been hit 17 times so far.\n",
      "\n",
      "  warnings.warn(msg, UserWarning)\n",
      "C:\\Users\\goodboy\\AppData\\Local\\Programs\\Python\\Python39\\lib\\site-packages\\cvxpy\\expressions\\expression.py:593: UserWarning: \n",
      "This use of ``*`` has resulted in matrix multiplication.\n",
      "Using ``*`` for matrix multiplication has been deprecated since CVXPY 1.1.\n",
      "    Use ``*`` for matrix-scalar and vector-scalar multiplication.\n",
      "    Use ``@`` for matrix-matrix and matrix-vector multiplication.\n",
      "    Use ``multiply`` for elementwise multiplication.\n",
      "This code path has been hit 18 times so far.\n",
      "\n",
      "  warnings.warn(msg, UserWarning)\n"
     ]
    }
   ],
   "source": [
    "#6.2\n",
    "\n",
    "#目标函数：收入max，约束：重量限制\n",
    "import cvxpy as cp\n",
    "import numpy as np\n",
    "c = np.array([-3,-5,-2,-4,-2,-3]) #定义目标向量\n",
    "a = np.array([8,13,6,9,5,7])#定义约束矩阵\n",
    "b = np.array([24])#定义右边约束矩阵\n",
    "x = cp.Variable(6,integer=True)#定义六个整型变量\n",
    "obj = cp.Minimize(c*x)#构造目标函数\n",
    "cons =[a*x <= b,x>=0,x<=1]#构造约束条件\n",
    "prob = cp.Problem(obj,cons)#构造问题模型\n",
    "prob.solve(solver = 'GLPK_MI',verbose = True)#求解问题\n",
    "print('总收入最优值为：',-prob.value)\n",
    "print('选运最优解为',x.value)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "#6.3\n",
    "\n",
    "#https://blog.csdn.net/qq_29831163/article/details/89387723?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165326505116782395338282%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165326505116782395338282&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-89387723-null-null.142^v10^pc_search_result_control_group,157^v4^control&utm_term=%E9%9D%A2%E8%AF%95%E9%A1%BA%E5%BA%8F%E9%97%AE%E9%A2%98&spm=1018.2226.3001.4187\n",
    "#python没有实现，不太会解这类模型，找到csdn上的lingo求解模型\n",
    "'''\n",
    "安排4名同学的面试顺序，使完成全部面试花费的时间最少\n",
    "t[i][j]表示第i名同学参加第j阶段面试所需要的时间,x[i][j]表示第i个同学参加第j阶段面试的开始时间\n",
    "目标函数即是完成全部面试所花费的最少时间minT={maxi(x[i][3],+t[i][3])}\n",
    "'''"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最优解为 [50. 60. 70.]\n",
      "最优值为 11279.999999974612\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\goodboy\\AppData\\Local\\Programs\\Python\\Python39\\lib\\site-packages\\cvxpy\\expressions\\expression.py:593: UserWarning: \n",
      "This use of ``*`` has resulted in matrix multiplication.\n",
      "Using ``*`` for matrix multiplication has been deprecated since CVXPY 1.1.\n",
      "    Use ``*`` for matrix-scalar and vector-scalar multiplication.\n",
      "    Use ``@`` for matrix-matrix and matrix-vector multiplication.\n",
      "    Use ``multiply`` for elementwise multiplication.\n",
      "This code path has been hit 122 times so far.\n",
      "\n",
      "  warnings.warn(msg, UserWarning)\n",
      "C:\\Users\\goodboy\\AppData\\Local\\Programs\\Python\\Python39\\lib\\site-packages\\cvxpy\\expressions\\expression.py:593: UserWarning: \n",
      "This use of ``*`` has resulted in matrix multiplication.\n",
      "Using ``*`` for matrix multiplication has been deprecated since CVXPY 1.1.\n",
      "    Use ``*`` for matrix-scalar and vector-scalar multiplication.\n",
      "    Use ``@`` for matrix-matrix and matrix-vector multiplication.\n",
      "    Use ``multiply`` for elementwise multiplication.\n",
      "This code path has been hit 123 times so far.\n",
      "\n",
      "  warnings.warn(msg, UserWarning)\n",
      "C:\\Users\\goodboy\\AppData\\Local\\Programs\\Python\\Python39\\lib\\site-packages\\cvxpy\\expressions\\expression.py:593: UserWarning: \n",
      "This use of ``*`` has resulted in matrix multiplication.\n",
      "Using ``*`` for matrix multiplication has been deprecated since CVXPY 1.1.\n",
      "    Use ``*`` for matrix-scalar and vector-scalar multiplication.\n",
      "    Use ``@`` for matrix-matrix and matrix-vector multiplication.\n",
      "    Use ``multiply`` for elementwise multiplication.\n",
      "This code path has been hit 124 times so far.\n",
      "\n",
      "  warnings.warn(msg, UserWarning)\n",
      "C:\\Users\\goodboy\\AppData\\Local\\Programs\\Python\\Python39\\lib\\site-packages\\cvxpy\\expressions\\expression.py:593: UserWarning: \n",
      "This use of ``*`` has resulted in matrix multiplication.\n",
      "Using ``*`` for matrix multiplication has been deprecated since CVXPY 1.1.\n",
      "    Use ``*`` for matrix-scalar and vector-scalar multiplication.\n",
      "    Use ``@`` for matrix-matrix and matrix-vector multiplication.\n",
      "    Use ``multiply`` for elementwise multiplication.\n",
      "This code path has been hit 125 times so far.\n",
      "\n",
      "  warnings.warn(msg, UserWarning)\n"
     ]
    }
   ],
   "source": [
    "#6.4\n",
    "'''\n",
    "先总结：这个问题中，约束都很清晰，但是默认cvxpy.solve求解器无法求解\n",
    "可以更换求解器进行求解（若未安装，需要安装）：\n",
    "# Solve with ECOS\n",
    "# Solve with ECOS_BB\n",
    "# Solve with CVXOPT\n",
    "# Solve with SCS\n",
    "# Solve with GLPK\n",
    "# Solve with GLPK_MI\n",
    "# Solve with GUROBI\n",
    "# Solve with MOSEK\n",
    "# Solve with Elemental\n",
    "# Solve with CBC\n",
    "'''\n",
    "'''\n",
    "每个季度生产能力 <= 100\n",
    "第一季度：x1>=40\n",
    "第二季度：(x1-40)+x2>=60\n",
    "第三季度：(x1-40)+x2-60+x3 = 80\n",
    "目标函数：min z = 50x1+0.2x2**2+4(x1-40)+50x2+0.2x2**2+4(x1+x2-100)+50x3+0.2x3**2\n",
    "'''\n",
    "import numpy as np\n",
    "import cvxpy as cp\n",
    "c1= np.array([0.2,0.2,0.2])\n",
    "c2 = np.array([58,54,50])\n",
    "a = np.array([[-1,0,0],[-1,-1,0],[1,0,0],[0,1,0],[0,0,1],[0,-1,0],[0,0,-1]])\n",
    "b = np.array([-40,-100,100,100,100,0,0])\n",
    "x = cp.Variable(3, integer=True)\n",
    "obj = cp.Minimize(c1*x**2+c2*x-560)\n",
    "Aeq = np.array([1,1,1])\n",
    "Beq = np.array([180])\n",
    "con =[a*x <= b, Aeq*x == Beq]\n",
    "prob = cp.Problem(obj,con)\n",
    "prob.solve(solver=cp.ECOS_BB)\n",
    "print('最优解为',x.value)\n",
    "print('最优值为',prob.value)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "eigenvalues:  [12.17597107 -2.50728797 -3.6686831 ]\n",
      "eigenvectors:  [[ 0.49659978  0.80958546 -0.31298568]\n",
      " [ 0.57735027 -0.57735027 -0.57735027]\n",
      " [ 0.64811675 -0.10600965  0.7541264 ]]\n"
     ]
    }
   ],
   "source": [
    "#6.5\n",
    "#二次函数的极值问题，即求二次型矩阵的特征值即可\n",
    "#A = [[1,4,5],[4,2,6],[5,6,3]],x1^2+x2^2+x3^2=1\n",
    "import numpy as np\n",
    "P = np.array([[1,4,5],[4,2,6],[5,6,3]])\n",
    "eigenvalues, eigenvectors = np.linalg.eig(P)#求特征值和特征向量\n",
    "print(\"eigenvalues: \", eigenvalues)\n",
    "print(\"eigenvectors: \", eigenvectors)\n",
    "#所以最大值为12.17"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最优值为: 275.0\n",
      "最优解为： [[1. 0. 0.]\n",
      " [0. 1. 0.]\n",
      " [0. 0. 1.]]\n"
     ]
    }
   ],
   "source": [
    "#6.6\n",
    "\n",
    "#即max服务人数 and max服务满意度\n",
    "'''\n",
    "x[i][j] = 0或者1  表示指派第i（i = 1,2,3）人，去完成第j（j = 1,2,3）项任务\n",
    "x[i][1]+x[i][2]+x[i][3] = 1\n",
    "x[i][1]+x[i][2]+x[i][3] = 1\n",
    "目标函数： max c[i][j]*x[i][j]*d[i][j]\n",
    "'''\n",
    "#可以利用人数*满意度决定 决定最终的安排\n",
    "# Solve with ECOS\n",
    "# Solve with ECOS_BB\n",
    "# Solve with CVXOPT\n",
    "# Solve with SCS\n",
    "# Solve with GLPK\n",
    "# Solve with GLPK_MI\n",
    "# Solve with GUROBI\n",
    "# Solve with MOSEK\n",
    "# Solve with Elemental\n",
    "# Solve with CBC\n",
    "import cvxpy as cp\n",
    "import numpy as np\n",
    "c = np.array( [[120,96,100],\n",
    "              [72,75,81],\n",
    "              [54,50,80]])\n",
    "x = cp.Variable((3,3),integer = True)\n",
    "obj = cp.Minimize(cp.sum(cp.multiply(-c,x)))\n",
    "con = [0 <= x, x <= 1, cp.sum(x, axis = 0, keepdims = True) == 1,\n",
    "                       cp.sum(x, axis = 1, keepdims = True) == 1]\n",
    "prob = cp.Problem(obj, con)\n",
    "prob.solve(solver = 'GLPK_MI')\n",
    "print(\"最优值为:\", -prob.value)\n",
    "print(\"最优解为：\", x.value)\n",
    "#所以最终安排第一个在第一个位置，第二个人在第二个位置，第三个人在第三个位置\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}